#ifndef _LGYALLOC_H
#define _LGYALLOC_H

/*
 * autor: 卢广宇
 * time: 2021/11/6
 *
 * function: 内存分配相关接口定义。
 * 			 使用二级分配策略。当大于128B时，采用从直接从堆上分配发的方法。
 			 当小于1等于28时，采用内存池和自由链表的分配方式，从而减少碎片化带来的影响。
 */

#include <cstdlib>  //for malloc free
#include <cstddef>  //for size_t 
#include <iostream>

using namespace::std;

namespace lgy
{

#if defined USE_MY_MALLOC  //本人实现的堆分配器
	#define Malloc(size) 	my_malloc(size)
	#define Free(p) 		my_free(p)
#else
	#define Malloc(size) 	malloc(size)
	#define Free(p) 		free(p)
#endif

//一级分配器
//template <int ins>
class __malloc_alloc
{

private:
	//oom:out of memory
	static void* oom_malloc(size_t size);			//处理oom
	static void (* malloc_alloc_oom_handel)();		//用户自定处理方法,若不定义则抛出bad alloc异常
public:
	static void* allocate(size_t size){
		void *p = NULL;

		if((p = Malloc(size)) == NULL){
			cerr<<"malloc fail"<<endl;
			
		}

		return p;
	}

	static void deallocate(void *p, size_t size){
		Free(p);	
	}

	//替换用户的处理方，并返回就方法
	static void (* set_malloc_alloc_handel(void (*fun)()))(){
		void (*old)() = malloc_alloc_oom_handel;

		malloc_alloc_oom_handel = fun;

		return old;
	}

};
//template <int ins>
void (* __malloc_alloc::malloc_alloc_oom_handel)() = 0;


//template <int ins>
class __default_alloc
{
private:
	enum {_ALIGN = 8};			//对齐边界,连续2块大小差
	enum {_MAX_BYTES = 128};	//最大块
	enum {_NFREELISTS = _MAX_BYTES/_ALIGN};	//空闲链表数量
	enum {_NOBJS = 20};			//每次填充的块数
private:
	//向上跳转到_ALIGN的倍数
	static size_t ROUND_UP(size_t size){
		return (size+_ALIGN-1) & ~(_ALIGN-1);
	}
	//定位free_list下标
	static size_t FREELIST_INDEX(size_t size){
		return (size+_ALIGN-1)/_ALIGN-1;
	}

private:
	static int refill(size_t n);		//调用chunk_alloc从内存池取出内存并填充到空闲链表中
	static char* chunk_alloc(size_t n, size_t &nobjs);	//从内存池取出n*nobjs字节大小内存
public:
	static void* allocate(size_t size);
	static void deallocate(void *p, size_t size);

private:
	//内存池(像水池一样)
	static char* mem_start;		//内存池起始地址
	static char* mem_end;		//内存池结束地址

private:
	union obj{	//free链表头元素
		union obj *next;  //指向下个空闲块
		char data[1];	//当分配出去时，next字段无效	
	};
	static obj* free_list[_NFREELISTS];	
};

char* __default_alloc::mem_start = 0;

char* __default_alloc::mem_end = 0;

__default_alloc::obj* __default_alloc::free_list[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

char* __default_alloc::chunk_alloc(size_t n, size_t &nobjs)
{
	char *chunk;
	size_t ntotal = n*nobjs;
	size_t nleft = mem_end - mem_start;

	//内存足够
	if(nleft > ntotal){
		mem_start += ntotal;
		return mem_start;
	}
	//至少可以分配一个
	else if(nleft >= n){
		nobjs = nleft/n;
		mem_start += nobjs*n;
		return mem_start;
	}
	//不足一个
	else{
		//把内存池剩余的分给其它空闲链表
		if(nleft > 0){
			obj** first = &free_list[FREELIST_INDEX(nleft)];
			((obj *)mem_start)->next = *first;
			*first = (obj *)mem_start;
			mem_start = mem_end;
		}
		size_t nalloc = 2*ntotal;	//要从堆申请的内存大小
		//申请失败，从free_list取出其它空闲块使用
		if((mem_start = (char *)malloc(nalloc)) == NULL){
			for(int i=n; i<_MAX_BYTES; i+=_ALIGN){
				obj** first = &free_list[FREELIST_INDEX(i)];
				if(first != 0){
					mem_start = (char *)(*first);
					mem_end = mem_start + i;
					*first = (*first)->next;
					return chunk_alloc(n, nobjs);
				}
			}
				
			nobjs = 0;
			return 0;
		}
		mem_end = mem_start + nalloc;
		return chunk_alloc(n, nobjs);
	}

	return 0;
}

//填充free_list[i]
//返回0：成功，-1：失败
int __default_alloc::refill(size_t n)
{	
	int i=0;
	size_t nobjs = _NOBJS;	
	char* chunk;
	obj *first;
	obj **list = &free_list[FREELIST_INDEX(n)];

	chunk = chunk_alloc(n, nobjs);
	*list = first = (obj*)chunk;
	if(nobjs == 0) return -1;
	for(i=0; i<nobjs-1; i++){
		first->next = first+n;	
		first += n;
	}
	first->next = 0;

	return 0;
}

void* __default_alloc::allocate(size_t size)
{
	size_t index = FREELIST_INDEX(size);
	obj* result;

	//大于_MAX_BYTES转一级分配
	if(size > _MAX_BYTES){
		return __malloc_alloc::allocate(size);
	}
	//空闲链表为空
	if(free_list[index] == 0){
		if(refill(ROUND_UP(size))==-1){
			return NULL;
		}
	}
	result = free_list[index];
	free_list[index] = result->next;

	return (void*)result;
}

//释放块，头插到相应的空闲链表
void __default_alloc::deallocate(void* p, size_t size)
{
	obj* q = (obj*)p;
	int index = FREELIST_INDEX(size);

	if(size > _MAX_BYTES){
		__malloc_alloc::deallocate(p, size);
		return;
	}

	//头插
	q->next = free_list[index];
	free_list[index] = q;
}

//对一级，二级的简单封装
template <typename T, typename Alloc>
class simply_alloc
{
public:
	static T* allocate(size_t n){
		return n==0?(T*)Alloc::allocate(n*sizeof(T)):0;
	}
	static T* allocate(){
		return (T*)Alloc::allocate(sizeof(T));
	}
	static void dealloacte(T* p, size_t n){
		if(n!=0) Alloc::deallocate(p, n*sizeof(T));
	}
	static void dealloacte(T* p){
		Alloc::deallocate(p, sizeof(T));
	}
};


//使用一级分配器。该宏由用户定义，系统默认使用二级分配器
#ifdef USE_MALLOC_ALLOC
	typedef __malloc_alloc alloc;
#else
	typedef __default_alloc alloc;
#endif


};

#endif

